#include <iostream>
#include <cstdlib>
#include <omp.h>

using namespace std;

template <class T>
void parqsort ( T *a, int first, int last, 
		int (*cmp) ( T, T ), void (*swap)( T*, T* ) ) {

    int i = first + 1;
	int j = last;
    T p = a[first];				// pivot

	if (i > j) return;			// terminating condition

    while (i <= j) {
        while (cmp(a[i], p) <= 0 && i <= last) i++;  // Approach from left
        while (cmp(a[j], p) == 1 && j >= first) j--; // Approach from right
		if (i < j) swap(&a[i], &a[j]);
    } 

	swap(&a[first], &a[j]);
    #pragma omp parallel sections
    {
        #pragma omp section
        parqsort(a, first, j-1, cmp, swap);
        
		#pragma omp section
        parqsort(a, j+1, last, cmp, swap);
    }
}

